package algorithms.leaning.class01;

import common.util.MyUtil;

/**
 * 无序数组，有正有负有0，任意两相邻数不等
 * 任意一个位置i，nums[i] < nums[i+1] && nums[i] < nums[i-1]就称i为局部最小
 *
 * @author guichang
 * @date 2021/5/30
 */

@SuppressWarnings("all")
public class Code6_二分_局部最小 {

    public static void main(String[] args) {
        int[] nums = MyUtil.createRandomArray(10, 0, 30);
        MyUtil.print(localMinimum(nums));
    }

    public static int localMinimum(int[] nums) {
        if (nums == null || nums.length < 2) {
            return -1;
        }
        int N = nums.length;
        // 若0位置符合则返回0位置
        if (nums[0] < nums[1]) {
            return nums[0];
        }
        // 若N-1位置符合则返回N-1位置
        if (nums[N - 1] < nums[N - 2]) {
            return nums[N - 1];
        }
        int left = 1, right = N - 2, mid = 0;
        while (left < right) {
            mid = left + ((right - left) >> 1);
            if (nums[mid] > nums[mid - 1]) {
                right = mid - 1;
            } else if (nums[mid] > nums[mid + 1]) {
                left = mid + 1;
            } else {
                // 找到了
                return mid;
            }
        }
        return left;
    }

}